package com.job.youka;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

/**
 * @author angzhijin
 * @Description
 * @create 2022-09-06 7:27 PM
 */
public class Youka0906 {

    public static void main(String[] args) {
        System.out.println(removeDuplicates("deeedbbcccbdaa",3));
    }


    public String alternativeMerge2 (String str1, String str2) {
        // write code here
        int len1 = str1.length();
        int len2 = str2.length();
        StringBuffer sb = new StringBuffer();
        for (int i = 0, j=0; i < len1; i++) {
            sb.append(str1.charAt(i));
            sb.append(str2.charAt(j));
            if(++j>=len2)
                j=0;
        }
        return sb.toString();
    }

    Stack<TreeNode> stack = new Stack<>();
    public ArrayList<TreeNode> findCommonAncestors2 (TreeNode root, TreeNode p, TreeNode q) {
        // write code here
        ArrayList<TreeNode> list = new ArrayList<>();
        dfs(root, p,q);
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }

    public TreeNode dfs(TreeNode root, TreeNode p, TreeNode q){
        if(root ==null) return null;
        if(root.val==p.val || root.val ==q.val) return root; // 需要用val比较
        TreeNode left = dfs(root.left, p, q);
        TreeNode right = dfs(root.right, p, q);

        if(left!=null && right!=null) {
            stack.push(root);
            return root;
        }
        if(left != null) {
            if(!stack.isEmpty())
                stack.push(root);
            return left;
        }
        if(right != null){
            if(!stack.isEmpty())
                stack.push(root);
            return right;
        }
        return null;
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
          this.val = val;
        }
    }


    public static String removeDuplicates (String s, int k) {
        // write code here

        StringBuffer sb = new StringBuffer(s);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < sb.length(); i++) {
            if(i==0 || stack.isEmpty()){
                stack.push(1);
            }else{
                if(sb.charAt(i) == sb.charAt(i-1)){
                    int count = stack.pop() +1;
                    stack.push(count);
                }else{
                    int count = stack.peek();
                    if(count>=k){
                        sb.delete(i-count, i);
                        i = i-count-1;
                        stack.pop();
                    }else{
                        stack.push(1);
                    }
                }
            }
        }
        return sb.toString();
    }
}
